#include <iostream>
#include <string>
#include <fstream>
#include <vector>

namespace part1
{

    std::vector<int> getSequence(const std::string& line)
    {
        std::vector<int> numbers {};
        std::size_t index {0};

        while (index < line.size())
        {
            if (line[index] == ' ')
            {
                index += 1;
                continue;;
            }

            // Find next ' '
            std::size_t pos {index + 1};
            while (true)
            {
                if (pos >= line.size() || line[pos] == ' ')
                    break;
                pos += 1;
            }
            numbers.emplace_back(std::stoi(&(line[index])));
            index = pos;
        }

        return numbers;
    }

    std::vector<std::vector<int>> getSequences(const std::string& filename)
    {
        std::ifstream file {filename};
        std::string line {};
        std::vector<std::vector<int>> sequences {};

        while (std::getline(file, line))
            sequences.emplace_back(getSequence(line));
        
        return sequences;
    }

    std::vector<int> getDifference(const std::vector<int>& sequence)
    {
        std::vector<int> difference {};
        for (std::size_t i = 0; i < sequence.size() - 1; ++i)
            difference.emplace_back(sequence[i + 1] - sequence[i]);
        return difference;
    }

    bool isSequenceAllZero(const std::vector<int>& sequence)
    {
        for (int number : sequence)
            if (number != 0) return false;
        return true;
    }

    int getHistory(const std::vector<int>& sequence)
    {
        std::vector<std::vector<int>> differences {};
        differences.emplace_back( getDifference(sequence) );

        // Get difference until all zero
        while (true)
        {
            const std::vector<int>& backSequence {differences.back()};
            if (isSequenceAllZero(backSequence))
                break;
            differences.emplace_back(getDifference(backSequence));
        }

        // Get history
        differences.back().emplace_back(0);
        auto iter = ++differences.rbegin();
        for (; iter != differences.rend(); ++iter)
        {
            auto pre {iter - 1};
            iter->emplace_back( pre->back() + iter->back() );
        }
        
        return differences.begin()->back() + sequence.back();
    }

    int getHistorysSum(const std::vector<std::vector<int>>& sequences)
    {
        int result {0};
        for (const std::vector<int>& sequence : sequences)
            result += getHistory(sequence);
        return result;
    }

    void solute()
    {
        auto sequences {getSequences("./src/day09/input.txt")};
        std::cout << getHistorysSum(sequences) << std::endl;
    }
}